package org.demo.algorithm;
/**
 * 队列的实现
 * @author  
 * @date    2011-4-24
 * @file    org.demo.algorithm.Queue.java
 */
public class Queue<E> {
	
	private E[] array;
	
	// 队列容量
	private int capacity = 10;
	
	// 当前队列大小
	private int size = 0;
	
	// 自动增长
	private boolean autoGrow = false;
	
	/**
	 * 构造方法
	 */
	@SuppressWarnings("unchecked")
	public Queue(){
		array = (E[])new Object[capacity];
	}
	
	@SuppressWarnings("unchecked")
	public Queue(int capacity){
		this.capacity = capacity;
		array = (E[])new Object[capacity];
	}
	
	@SuppressWarnings("unchecked")
	public Queue(int capacity, boolean autoGrow){
		this.capacity = capacity;
		this.autoGrow = autoGrow;
		array = (E[])new Object[capacity];		
	}
	
	/**
	 * 入队列
	 * @param e
	 * @return
	 */
	public Queue<E> offer(E e){
		if (isFull()){
			if (autoGrow){
				expand();
			} else {
				throw new RuntimeException("队列只能存储 " + size + " 个元素，已满");
			}
		}
		array[size++] = e;
		return this;
	}
	/**
	 * 出队列
	 * @return
	 */
	public E poll(){
		if (size == 0){
			throw new RuntimeException("队列已空！");
		}
		E e = array[0];
		size--;
		for (int i=0; i<size; i++){
			array[i] = array[i+1];
		}		
		array[size] = null;
		return e;
	}
	/**
	 * 队列已满
	 * @return
	 */
	public boolean isFull(){
		return size == capacity;
	}
	/**
	 * 队列已空
	 * @return
	 */
	public boolean isEmpty(){
		return size == 0;
	}
	/**
	 * 扩展队列
	 */
	@SuppressWarnings("unchecked")
	private void expand(){
		capacity = capacity * 2;
		E[] newArr = (E[])new Object[capacity];
		for (int i=0; i<size; i++){
			newArr[i] = array[i];
		}
		array = newArr;		
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Queue<String> queue = new Queue<String>(2, true);
		queue.offer("1").offer("2").offer("3");
		while (!queue.isEmpty()){
			String val = queue.poll();
			System.out.println(val);
		}
	}

}
